numQueue = [1,2,3,4,5,6,7,8,9]
resultStack = []
checkPoint = [2, 5, 6, 7, 8]
ROWS = 3
COLS = 3

SUM = 15

board = [[0 for r in range(ROWS)] for c in range(COLS)]

def GetRowColFromIndex(idx):
    r = int(idx / ROWS)
    c = int(idx % ROWS)
    return r, c

# 当前要放置的数字是否合法
def IsFillingValueValid(cur_index, val):
    global checkPoint, board
    if not cur_index in checkPoint:
        # 不是check_point的话就随便放
        return  True

    r, c = GetRowColFromIndex(cur_index)

    # 是check_point的话要进行合法性校验
    if cur_index == 2 or cur_index == 5:
        if board[r][0] + board[r][1] + val == SUM:
            return True
    elif cur_index == 6:
        if board[0][c] + board[1][c] + val == SUM and board[0][2] + board[1][1] + val == SUM:
            return True
    elif cur_index == 7:
        if board[0][c] + board[1][c] + val == SUM:
            return True
    elif cur_index == 8:
        if board[0][c] + board[1][c] + val == SUM and board[r][0] + board[r][1] + val == SUM and board[0][0] + board[1][1] + val == SUM:
            return True

    return False

# 获取比输入数字大1且没有使用过的数字
def GetBiggerUnusedNum(num):
    while num < 9:
        num += 1

        if num in numQueue:
           return num 
    
    # 没有找到符合要求的数字
    return -1

def CalcCheckPointNum(curIndex):
    global board, numQueue
    r, c = GetRowColFromIndex(curIndex)
    ret = -1
    if curIndex == 2:
        cp = SUM - board[0][0] - board[0][1]
        if cp in numQueue:
            ret = cp
    elif curIndex == 5:
        cp = SUM - board[1][0] - board[1][1]
        if cp in numQueue:
            ret = cp
    elif curIndex == 6:
        cp = SUM - board[0][0] - board[1][0]
        if cp in numQueue and cp + board[1][1] + board[0][2] == SUM:
            ret = cp
    elif curIndex == 7:
        cp = SUM - board[0][1] - board[1][1]
        if cp in numQueue:
            ret = cp
    elif curIndex == 8:
        cp = SUM - board[2][1] - board[2][0]
        if cp in numQueue and cp + board[1][1] + board[0][0] == cp + board[1][2] + board[0][2] == SUM:
            ret = cp

    return ret

def PutNum(curIndex, num):
    global board, numQueue
    r, c = GetRowColFromIndex(curIndex)
    board[r][c] = num
    resultStack.append((curIndex, num))
    numQueue.remove(num)

def main():
    global board, numQueue
    # 当前要填的格子
    curIndex = 0

    while len(numQueue) > 0:
        # 如果index in checkPoint，则自动补最后一个数字
        r, c = GetRowColFromIndex(curIndex)
        needRollBack = False
        if board[r][c] == 0:
            num = min(numQueue)
            if IsFillingValueValid(curIndex, num) == True:
                # 合法包括两种情况，一种是非checkpoint, 一种是合法的checkpoint
                PutNum(curIndex, num)
            else:
                # 否则计算checkpoint上究竟应该放数字几
                # 如果所需的数字不存在则触发回溯
                checkPointNum = CalcCheckPointNum(curIndex)
                if checkPointNum == -1:
                    needRollBack = True
                else:
                    PutNum(curIndex, checkPointNum)

            if needRollBack == True:
                # 不合法，进行回溯
                while True:
                    info = resultStack.pop()
                    rollBackIndex = info[0]
                    num = info[1]
                    rr, cc = GetRowColFromIndex(rollBackIndex)
                    numQueue.append(num)
                    nextNum = GetBiggerUnusedNum(num)
                    if nextNum != -1 and IsFillingValueValid(rollBackIndex, nextNum) == True:
                        PutNum(rollBackIndex, nextNum)
                        break
                    
                    # 如果nextNum == -1，则清理[rr][cc]继续回溯
                    board[rr][cc] = 0
                curIndex = rollBackIndex + 1
            else:
                curIndex += 1

    for r in range(ROWS):
        print(board[r])

main()